package discrete.math;

import java.util.ArrayList;

/**
 * Determine the number of paths based on the size of the paths and 2 points.
 * Determine the actual paths based on the size and the 2 points
 * 
 */
public class Paths {

    static int[][] newMatrix;
    ArrayList<String> paths;

    /**
     * Receives a filled matrix, two vertices, and size of path to calculate.
     * Returns the numbers of paths
     * 
     * @param matrix
     *            a filled matrix
     * @param sizePath
     *            number of paths
     * @param vertix1
     *            the row to calculate path
     * @param vertix2
     *            the column to calculate path
     * @return number of paths to the 2 vertices based on the size of path
     */
    public Paths(MatrixMath matrix) {
        newMatrix = new int[matrix.getMrows() - 1][matrix.getMcolumns() - 1];
        newMatrix = trimMatrix(matrix);
        paths = new ArrayList<String>();
    }

    private int[][] trimMatrix(MatrixMath matrix) {
        for (int i = 0; i < matrix.getMrows() - 1; i++) {
            for (int j = 0; j < matrix.getMcolumns() - 1; j++) {
                newMatrix[i][j] = matrix.lmatrix[i + 1][j + 1];
            }
        }
        return newMatrix;
    }

    /**
     * Creates all the know paths based on the starting and end points that is
     * given
     * 
     * @param matrix
     *            the matrix to find the paths
     * @param start
     *            start character ex. 'A'
     * @param end
     *            end character ex. 'B'
     * @param pathLength
     *            length of the paths to find
     * @param numVertices
     *            the number of vertices in the matrix
     * @return
     */
    public ArrayList<String> createPaths(char start, char end, int pathLength,
            int numVertices) {
        StringBuffer buffer = new StringBuffer(""); // always needs one n
        // String[] c = new String[pathLength + 1];

        buffer.append(start);
        buffer.append(start);
        for (int i = 0; i < pathLength; i++) {
            buffer.append('A');
        }
        int offset = buffer.length() - 1;
        while (buffer.charAt(0) == start) {
            System.out.println(buffer.substring(1));
            buffer.setCharAt(offset, (char) (buffer.charAt(offset) + 1));
            // Check if character went out of range, and bump
            for (int i = offset; i >= 0; i--) {
                if (buffer.charAt(i) > 'A' + numVertices) {
                    buffer.setCharAt(i, 'A');
                    buffer.setCharAt(i - 1, (char) (buffer.charAt(i - 1) + 1));
                } else {
                    break;
                }
            }
            String str = new String(buffer.substring(1));
            if (checkPath(str, start, end, numVertices)) {
                paths.add(str);
                System.out.println(buffer.substring(1));
            }
        }

        return paths;
    }

    /**
     * Checks to see if the paths are good
     * 
     * @param string
     *            the string containing the path
     * @param startPoint
     *            starting point
     * @param endPoint
     *            ending point
     * @param numVertices
     *            number of vertices in the matrix
     * @return true if the path is good
     */
    private boolean checkPath(String string, char startPoint, char endPoint,
            int numVertices) {
        Boolean result = true;

        // check to see if start matches actual start
        if (string.charAt(0) != startPoint) {
            return false;
        // check to see if the end matches the actual end
        } else if (string.charAt(string.length() - 1) != endPoint) {
            return false;
        } else {
            // checks for any duplicate points and out of range
            for (int i = 0; i < string.length(); i++) {
                if (i >= 0 && i <= string.length() - 2) {
                    if (string.charAt(i) == string.charAt(i + 1) || string.charAt(i) >= numVertices + 65) {
                        return false;
                    }
                }
            }
            // this is to remove invalid paths based on the matrix
            int j, k;
            for (int i = 0; i < string.length(); i++) {
                if (i >= 0 && i <= string.length() - 2) {
                    j = string.charAt(i) - 65;
                    k = string.charAt(i + 1) - 65;
                    if (j >= 0 && j <= newMatrix.length - 1) {
                        if (k >= 0 && k <= newMatrix.length - 1) {
                            if (newMatrix[j][k] == 0) {
                                return false;
                            }
                        }

                    }
                }

            }
        }
        return result;
    }

    /**
     * Calculates the number of paths give the matrix, size and the two vertices
     * 
     * @param matrix
     * @param sizePath
     * @param vertix1
     * @param vertix2
     * @return the number of paths
     */
    public static int numberPaths(int sizePath, int vertix1, int vertix2) {
        int[][] mulMatrix = new int[newMatrix.length][newMatrix.length];
        mulMatrix = newMatrix.clone();
        for (int i = 1; i < sizePath; i++) {
            mulMatrix = Paths.mmult(mulMatrix, newMatrix);
        }
        int result = 0;
        result = mulMatrix[vertix1][vertix2];
        return result;
    }

    /**
     * Multiplies the matrix based on the path length
     * 
     * @param A
     * @param pathLength
     * @return a new matrix with the calculated paths
     */
    static int[][] mmult(int[][] A, int[][] B) {
        int i, j, k; // loop counters

        int ax; // accumulator for matrix multiplication

        int[][] C = new int[A.length][A.length];
        for (i = 0; i < A.length; i++) {
            for (j = 0; j < A.length; j++) {
                ax = 0; // reset accumulator

                for (k = 0; k < A.length; k++) {
                    ax = ax + (A[i][k] * B[k][j]);
                }
                C[i][j] = ax;
            }
        }
        return C;
    }
    /**
     * Gets the number of vertices on the matrix
     * 
     * @param matrix
     * @return the number of vertices
     */
//	static int getNumberVertices(int[][] matrix) {
//		int result = 0;
//		result = matrix.length;
//		return result;
//	}
}
